from typing import List


class Solution:


    """
    方法：二分查找
    将二维矩阵转化为一维数组进行二分查找。利用整除和取余运算将一维索引映射回二维坐标。

    Args:
        matrix: List[List[int]], m x n 的二维矩阵
        target: int, 要搜索的目标值

    Returns:
        bool: 如果找到目标值返回True，否则返回False

    Time: O(log(mn))，其中m和n分别是矩阵的行数和列数
    
    Space: O(1)，只使用常数额外空间
    """
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = -1, m * n
        while left + 1 < right:
            mid = (left + right) // 2
            x = matrix[mid // n][mid % n]
            if x == target:
                return True
            if x < target:
                left = mid
            else:
                right = mid
        return False
    
    """
    方法：Z字形查找
    从矩阵的右上角开始搜索。如果当前元素小于目标值，则向下移动；如果大于目标值，则向左移动。
    利用矩阵的有序性质，每次可以排除一行或一列。

    Args:
        matrix: List[List[int]], m x n 的二维矩阵
        target: int, 要搜索的目标值

    Returns:
        bool: 如果找到目标值返回True，否则返回False

    Time: O(m + n)，其中m和n分别是矩阵的行数和列数，最坏情况下需要遍历m+n个元素
    
    Space: O(1)，只使用常数额外空间
    """
    def searchMatrix1(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1;
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            if matrix[i][j] < target:
                i += 1
            else:
                j -= 1
        return False